package sort;

public class CountSort {
	public static void main(String[] args) {
		// 排序的数组
		int a[] = { 100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95 };
		int b[] = countingSort(a, a.length);
		for (int i : b) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public static int[] countingSort(int[] A, int n) {
		count(A);
		return A;
	}

	public static void count(int[] arr) {
		int min = arr[0];
		int max = arr[0];
		for (int i = 1; i < arr.length; i++) {
			min = Math.min(arr[i], min);
			max = Math.max(arr[i], max);
		}
		int[] countArr = new int[max - min + 1];
		for (int i = 0; i < arr.length; i++) {
			countArr[arr[i] - min]++;
		}
		int index = 0;
		for (int i = 0; i < countArr.length; i++) {
			while (countArr[i]-- > 0) {
				arr[index++] = i + min;// i+min就是其对应的值
			}
		}
	}
}
